from random import *

class UbicadorDePalabras:
	
	DIRECCIONES = [(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]
	
	def ubicar(self, palabras, matrizDeLetras):
		alto = len(matrizDeLetras)
		ancho = len(matrizDeLetras[0])
		
		posicionesUsadas = self.__iniciarMatrizDePosiciones(ancho, alto)
		
		for palabra in palabras:
			self.__ubicarPalabra(palabra,matrizDeLetras, posicionesUsadas)
	
	def __iniciarMatrizDePosiciones(self, ancho, alto):
		posiciones = []
		for i in range(alto):
			posiciones.append([])
			for j in range(ancho):
				posiciones[i].append(' ')
		return posiciones
	
	def __ubicarPalabra(self, palabra, matriz, posicionesUsadas):
		alto = len(matriz)
		ancho = len(matriz[0])
		
		estaPuesta = False
		while not estaPuesta:
			(x0,y0) = self.__puntoRandom(ancho-1,alto-1)
			(dx,dy) = self.__direccionRandom()
			
			if 0 < (x0+dx*len(palabra)) and (x0+dx*len(palabra)) < ancho and 0 < (y0+dy*len(palabra)) and (y0+dy*len(palabra)) < alto :
				
				entra = True
				
				for i in range(len(palabra)):
					casilleroI = posicionesUsadas[x0+dx*i][y0+dy*i]
					if casilleroI != ' ' and casilleroI != palabra[i]:
						entra = False
						break
					
				if entra:
					for i in range(len(palabra)):
						posicionesUsadas[x0+dx*i][y0+dy*i] = palabra[i]
						matriz[x0+dx*i][y0+dy*i] = palabra[i]
					estaPuesta = True
	
	def __puntoRandom(self, anchoMax, altoMax):
		return ( randint(0,anchoMax), randint(0, altoMax) )
	
	def __direccionRandom(self):
		[direccion] = sample( self.DIRECCIONES, 1 )
		return direccion